package dp.子序列;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 最大整除子集368.java
 * @createTime 2024年03月22日 09:54:00
 */
public class 最大整除子集368 {
	public static List<Integer> largestDivisibleSubset(int[] nums) {
		Arrays.sort(nums);
		List<Integer>[] dp = new List[nums.length];
		//baseCase
		for (int i = 0; i < dp.length; i++) {
			dp[i]=new ArrayList<>();
		}
		dp[0].add(nums[0]);

		for (int i = 1; i < nums.length; i++) {
			int maxSubSize = 0, index = -1;
			//寻找dp[0]到dp[i]之间长度最长的数组
			for (int j = 0; j < i; j++) {
				if (nums[i] % nums[j] == 0 && dp[j].size() > maxSubSize) {
					maxSubSize = dp[j].size();
					index = j;
				}
			}
			if (index != -1) {
				dp[i].addAll(dp[index]);
			}
			dp[i].add(nums[i]);
		}
		List<Integer> maxList = dp[0];
		for (List<Integer> list : dp) {
			if (list.size() > maxList.size()) {
				maxList = list;
			}
		}
		return maxList;
	}

	public static void main(String[] args) {
		System.out.println(largestDivisibleSubset(new int[]{1,2,3}));;
	}
}
